package dp.test139;

import java.util.HashMap;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/23 9:46
 */
public class Solution1 {

    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    HashMap<Integer, Boolean> map = new HashMap<>();
    List<String> wordDict;

    public boolean wordBreak(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        if (wordDict.isEmpty()) return false;
        for (String t : wordDict) {
            min = Math.min(min, t.length());
            max = Math.max(max, t.length());
        }
        if (s.length() < min) return false;
        return dfs(s, 0, s.length());
    }

    private boolean dfs(String s, int c, int l) {
        if (c == l) return true;
        if (map.containsKey(c)) return map.get(c);
        for (int i = min; i <= max && c + i <= l; i++) {
            if (wordDict.contains(s.substring(c, c + i)) && dfs(s, c + i, l)) {
                map.put(c, true);
                return true;
            }
        }
        map.put(c, false);
        return false;
    }
}
